package com.code.leetcode.center50;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/26 16:05
 */
public class The329 {

    int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int[][] matrix;
    int m, n;
    int max;

    public int longestIncreasingPath(int[][] matrix) {
        this.matrix = matrix;
        m = matrix.length;
        if (m < 1 || matrix[0].length < 1) return 0;
        n = matrix[0].length;
        int[][] memo = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(max, dfs(i, j, memo)) ;
            }
        }
        return max;
    }

    private int dfs(int i, int j, int[][] memo) {
        if (memo[i][j] != 0)
            return memo[i][j];
        ++memo[i][j];
        for (int k = 0; k < 4; k++) {
            int X = i + direction[k][0];
            int Y = j + direction[k][1];
            if (isValid(X, Y) && matrix[X][Y] > matrix[i][j]) {
                 memo[i][j] = Math.max(memo[i][j], dfs(X, Y, memo) + 1);
            }
        }
        return memo[i][j];
    }

    private boolean isValid(int X, int Y) {
        return X >= 0 && X < m && Y >= 0 && Y < n;
    }


    public static void main(String[] args) {
        The329 the329 = new The329();
        System.out.println(the329.longestIncreasingPath(new int[][]{{3, 4, 5}, {3, 2, 6}, {2, 2, 1}}));
    }

}
